home *** CD-ROM | disk | FTP | other *** search
/ Power Programmierung / Power-Programmierung (Tewi)(1994).iso / magazine / drdobbs / ddjcompr / sixpack / sixpack.c < prev    next >
Text File  |  1991-04-20  |  14KB  |  505 lines
  1. /********************************************/
  2. /*  SIXPACK.C -- Data compression program   */
  3. /*  Written by Philip G. Gage, April 1991   */
  4. /********************************************/
  5.  
  6. #include <stdio.h>
  7. #include <alloc.h>        /* Use <malloc.c> for Power C */
  8.  
  9. #define TEXTSEARCH 1000   /* Max strings to search in text file */
  10. #define BINSEARCH   200   /* Max strings to search in binary file */
  11. #define TEXTNEXT     50   /* Max search at next character in text file */
  12. #define BINNEXT      20   /* Max search at next character in binary file */
  13. #define MAXFREQ    2000   /* Max frequency count before table reset */ 
  14. #define MINCOPY       3   /* Shortest string copy length */
  15. #define MAXCOPY      64   /* Longest string copy length */
  16. #define SHORTRANGE    3   /* Max distance range for shortest length copy */
  17. #define COPYRANGES    6   /* Number of string copy distance bit ranges */
  18. short copybits[COPYRANGES] = {4,6,8,10,12,14};   /* Distance bits */
  19.  
  20. #define CODESPERRANGE (MAXCOPY - MINCOPY + 1)
  21. int copymin[COPYRANGES], copymax[COPYRANGES];
  22. int maxdistance, maxsize;
  23. int distance, insert = MINCOPY, dictfile = 0, binary = 0;
  24.  
  25. #define NIL -1                    /* End of linked list marker */
  26. #define HASHSIZE 16384            /* Number of entries in hash table */
  27. #define HASHMASK (HASHSIZE - 1)   /* Mask for hash key wrap */
  28. short far *head, far *tail;       /* Hash table */
  29. short far *succ, far *pred;       /* Doubly linked lists */
  30. unsigned char *buffer;            /* Text buffer */
  31.  
  32. /* Define hash key function using MINCOPY characters of string prefix */
  33. #define getkey(n) ((buffer[n] ^ (buffer[(n+1)%maxsize]<<4) ^ \
  34.                    (buffer[(n+2)%maxsize]<<8)) & HASHMASK)
  35.  
  36. /* Adaptive Huffman variables */
  37. #define TERMINATE 256             /* EOF code */
  38. #define FIRSTCODE 257             /* First code for copy lengths */
  39. #define MAXCHAR (FIRSTCODE+COPYRANGES*CODESPERRANGE-1)
  40. #define SUCCMAX (MAXCHAR+1)
  41. #define TWICEMAX (2*MAXCHAR+1)
  42. #define ROOT 1
  43. short left[MAXCHAR+1], right[MAXCHAR+1];  /* Huffman tree */
  44. short up[TWICEMAX+1], freq[TWICEMAX+1];
  45.  
  46. /*** Bit packing routines ***/
  47.  
  48. int input_bit_count = 0;           /* Input bits buffered */
  49. int input_bit_buffer = 0;          /* Input buffer */
  50. int output_bit_count = 0;          /* Output bits buffered */
  51. int output_bit_buffer = 0;         /* Output buffer */
  52. long bytes_in = 0, bytes_out = 0;  /* File size counters */
  53.  
  54. /* Write one bit to output file */
  55. output_bit(output,bit)
  56.   FILE *output;
  57.   int bit;
  58. {
  59.   output_bit_buffer <<= 1;
  60.   if (bit) output_bit_buffer |= 1;
  61.   if (++output_bit_count == 8) {
  62.     putc(output_bit_buffer,output);
  63.     output_bit_count = 0;
  64.     ++bytes_out;
  65.   }
  66. }
  67.  
  68. /* Read a bit from input file */
  69. int input_bit(input)
  70.   FILE *input;
  71. {
  72.   int bit;
  73.  
  74.   if (input_bit_count-- == 0) {
  75.     input_bit_buffer = getc(input);
  76.     if (input_bit_buffer == EOF) {
  77.       printf(" UNEXPECTED END OF FILE\n");
  78.       exit(1);
  79.     }
  80.     ++bytes_in;
  81.     input_bit_count = 7;
  82.   }
  83.   bit = (input_bit_buffer & 0x80) != 0;
  84.   input_bit_buffer <<= 1;
  85.   return(bit);
  86. }
  87.  
  88. /* Write multibit code to output file */
  89. output_code(output,code,bits)
  90.   FILE *output;
  91.   int code,bits;
  92. {
  93.   int i;
  94.  
  95.   for (i = 0; i<bits; i++) {
  96.     output_bit(output,code & 0x01);
  97.     code >>= 1;
  98.   }
  99. }
  100.  
  101. /* Read multibit code from input file */
  102. int input_code(input,bits)
  103.   FILE *input;
  104.   int bits;
  105. {
  106.   int i, bit = 1, code = 0;
  107.  
  108.   for (i = 0; i<bits; i++) {
  109.     if (input_bit(input)) code |= bit;
  110.     bit <<= 1;
  111.   }
  112.   return(code);
  113. }
  114.  
  115. /* Flush any remaining bits to output file before closing file */
  116. flush_bits(output)
  117.   FILE *output;
  118. {
  119.   if (output_bit_count > 0) {
  120.     putc((output_bit_buffer << (8-output_bit_count)),output);
  121.     ++bytes_out;
  122.   }
  123. }
  124.  
  125. /*** Adaptive Huffman frequency compression ***/
  126.  
  127. /* Data structure based partly on "Application of Splay Trees
  128.    to Data Compression", Communications of the ACM 8/88 */
  129.  
  130. /* Initialize data for compression or decompression */
  131. initialize()
  132. {
  133.   int i, j;
  134.  
  135.   /* Initialize Huffman frequency tree */
  136.   for (i = 2; i<=TWICEMAX; i++) {
  137.     up[i] = i/2;
  138.     freq[i] = 1;
  139.   }
  140.   for (i = 1; i<=MAXCHAR; i++) {
  141.     left[i] = 2*i;
  142.     right[i] = 2*i+1;
  143.   }
  144.  
  145.   /* Initialize copy distance ranges */
  146.   j = 0;
  147.   for (i = 0; i<COPYRANGES; i++) {
  148.     copymin[i] = j;
  149.     j += 1 << copybits[i];
  150.     copymax[i] = j - 1;
  151.   }
  152.   maxdistance = j - 1;
  153.   maxsize = maxdistance + MAXCOPY;
  154. }
  155.  
  156. /* Update frequency counts from leaf to root */
  157. update_freq(a,b)
  158.   int a,b;
  159. {
  160.   do {
  161.     freq[up[a]] = freq[a] + freq[b];
  162.     a = up[a];
  163.     if (a != ROOT) {
  164.       if (left[up[a]] == a) b = right[up[a]];
  165.       else b = left[up[a]];
  166.     }
  167.   } while (a != ROOT);
  168.  
  169.   /* Periodically scale frequencies down by half to avoid overflow */
  170.   /* This also provides some local adaption and better compression */
  171.   if (freq[ROOT] == MAXFREQ)
  172.     for (a = 1; a<=TWICEMAX; a++) freq[a] >>= 1;
  173. }
  174.  
  175. /* Update Huffman model for each character code */
  176. update_model(code)
  177.   int code;
  178. {
  179.   int a, b, c, ua, uua;
  180.  
  181.   a = code + SUCCMAX;
  182.   ++freq[a];
  183.   if (up[a] != ROOT) {
  184.     ua = up[a];
  185.     if (left[ua] == a) update_freq(a,right[ua]);
  186.     else update_freq(a,left[ua]);
  187.     do {
  188.       uua = up[ua];
  189.       if (left[uua] == ua) b = right[uua];
  190.       else b = left[uua];
  191.  
  192.       /* If high freq lower in tree, swap nodes */
  193.       if (freq[a] > freq[b]) {
  194.         if (left[uua] == ua) right[uua] = a;
  195.         else left[uua] = a;
  196.         if (left[ua] == a) {
  197.           left[ua] = b; c = right[ua];
  198.         } else {
  199.           right[ua] = b; c = left[ua];
  200.         }
  201.         up[b] = ua; up[a] = uua;
  202.         update_freq(b,c); a = b;
  203.       }
  204.       a = up[a]; ua = up[a];
  205.     } while (ua != ROOT);
  206.   }
  207. }
  208.  
  209. /* Compress a character code to output stream */
  210. compress(output,code)
  211.   FILE *output;
  212.   int code;
  213. {
  214.   int a, sp = 0;
  215.   int stack[50];
  216.  
  217.   a = code + SUCCMAX;
  218.   do {
  219.     stack[sp++] = (right[up[a]] == a);
  220.     a = up[a];
  221.   } while (a != ROOT);
  222.   do {
  223.     output_bit(output,stack[--sp]);
  224.   } while (sp);
  225.   update_model(code);
  226. }
  227.  
  228. /* Uncompress a character code from input stream */
  229. int uncompress(input)
  230.   FILE *input;
  231. {
  232.   int a = ROOT;
  233.  
  234.   do {
  235.     if (input_bit(input)) a = right[a];
  236.     else a = left[a];
  237.   } while (a <= MAXCHAR);
  238.   update_model(a-SUCCMAX);
  239.   return(a-SUCCMAX);
  240. }
  241.  
  242. /*** Hash table linked list string search routines ***/
  243.  
  244. /* Add node to head of list */
  245. add_node(n)  
  246.   int n;
  247. {
  248.   int key;
  249.  
  250.   key = getkey(n);
  251.   if (head[key] == NIL) {
  252.     tail[key] = n;
  253.     succ[n] = NIL;
  254.   } else {
  255.     succ[n] = head[key];
  256.     pred[head[key]] = n;
  257.   }
  258.   head[key] = n;
  259.   pred[n] = NIL;
  260. }
  261.  
  262. /* Delete node from tail of list */
  263. delete_node(n)
  264.   int n;
  265. {
  266.   int key;
  267.  
  268.   key = getkey(n);
  269.   if (head[key] == tail[key])
  270.     head[key] = NIL;
  271.   else {
  272.     succ[pred[tail[key]]] = NIL;
  273.     tail[key] = pred[tail[key]];
  274.   }
  275. }
  276.  
  277. /* Find longest string matching lookahead buffer string */
  278. int match(n,depth)
  279.   int n,depth;
  280. {
  281.   int i, j, index, key, dist, len, best = 0, count = 0;
  282.  
  283.   if (n == maxsize) n = 0;
  284.   key = getkey(n);
  285.   index = head[key];
  286.   while (index != NIL) {
  287.     if (++count > depth) break;     /* Quit if depth exceeded */
  288.     if (buffer[(n+best)%maxsize] == buffer[(index+best)%maxsize]) {
  289.       len = 0;  i = n;  j = index;
  290.       while (buffer[i]==buffer[j] && len<MAXCOPY && j!=n && i!=insert) {
  291.         ++len;
  292.         if (++i == maxsize) i = 0;
  293.         if (++j == maxsize) j = 0;
  294.       }
  295.       dist = n - index;
  296.       if (dist < 0) dist += maxsize;
  297.       dist -= len;
  298.       /* If dict file, quit at shortest distance range */
  299.       if (dictfile && dist > copymax[0]) break;
  300.       if (len > best && dist <= maxdistance) {     /* Update best match */
  301.         if (len > MINCOPY || dist <= copymax[SHORTRANGE+binary]) {
  302.           best = len; distance = dist;
  303.         }
  304.       }
  305.     }
  306.     index = succ[index];
  307.   }
  308.   return(best);
  309. }
  310.  
  311. /*** Finite Window compression routines ***/
  312.  
  313. #define IDLE 0    /* Not processing a copy */
  314. #define COPY 1    /* Currently processing copy */
  315.  
  316. /* Check first buffer for ordered dictionary file */
  317. /* Better compression using short distance copies */
  318. dictionary()
  319. {
  320.   int i = 0, j = 0, k, count = 0;
  321.  
  322.   /* Count matching chars at start of adjacent lines */
  323.   while (++j < MINCOPY+MAXCOPY) {
  324.     if (buffer[j-1] == 10) {
  325.       k = j;
  326.       while (buffer[i++] == buffer[k++]) ++count;
  327.       i = j;
  328.     }
  329.   }
  330.   /* If matching line prefixes > 25% assume dictionary */
  331.   if (count > (MINCOPY+MAXCOPY)/4) dictfile = 1;
  332. }
  333.  
  334. /* Encode file from input to output */
  335. encode(input,output)
  336.   FILE *input, *output;
  337. {
  338.   int c, i, n=MINCOPY, addpos=0, len=0, full=0, state=IDLE, nextlen;
  339.  
  340.   initialize();
  341.   head = farmalloc((unsigned long)HASHSIZE*sizeof(short));
  342.   tail = farmalloc((unsigned long)HASHSIZE*sizeof(short));
  343.   succ = farmalloc((unsigned long)maxsize*sizeof(short));
  344.   pred = farmalloc((unsigned long)maxsize*sizeof(short));
  345.   buffer = (unsigned char *) malloc(maxsize*sizeof(unsigned char));
  346.   if (head==NULL || tail==NULL || succ==NULL || pred==NULL || buffer==NULL) {
  347.     printf("Error allocating memory\n");
  348.     exit(1);
  349.   }
  350.  
  351.   /* Initialize hash table to empty */
  352.   for (i = 0; i<HASHSIZE; i++) {
  353.     head[i] = NIL;
  354.   }
  355.  
  356.   /* Compress first few characters using Huffman */
  357.   for (i = 0; i<MINCOPY; i++) {
  358.     if ((c = getc(input)) == EOF) {
  359.       compress(output,TERMINATE);
  360.       flush_bits(output);
  361.       return(bytes_in);
  362.     }
  363.     compress(output,c);  ++bytes_in;
  364.     buffer[i] = c;
  365.   }
  366.  
  367.   /* Preload next few characters into lookahead buffer */
  368.   for (i = 0; i<MAXCOPY; i++) {
  369.     if ((c = getc(input)) == EOF) break;
  370.     buffer[insert++] = c;  ++bytes_in;
  371.     if (c > 127) binary = 1;     /* Binary file ? */
  372.   }
  373.   dictionary();  /* Check for dictionary file */
  374.  
  375.   while (n != insert) {
  376.     /* Check compression to insure really a dictionary file */
  377.     if (dictfile && ((bytes_in % MAXCOPY) == 0))
  378.       if (bytes_in/bytes_out < 2)
  379.         dictfile = 0;     /* Oops, not a dictionary file ! */
  380.  
  381.     /* Update nodes in hash table lists */
  382.     if (full) delete_node(insert);
  383.     add_node(addpos);
  384.  
  385.     /* If doing copy, process character, else check for new copy */
  386.     if (state == COPY) {
  387.       if (--len == 1) state = IDLE;
  388.     } else {
  389.  
  390.       /* Get match length at next character and current char */
  391.       if (binary) {
  392.         nextlen = match(n+1,BINNEXT);
  393.         len = match(n,BINSEARCH);
  394.       } else {
  395.         nextlen = match(n+1,TEXTNEXT);
  396.         len = match(n,TEXTSEARCH);
  397.       }
  398.  
  399.       /* If long enough and no better match at next char, start copy */
  400.       if (len >= MINCOPY && len >= nextlen) {
  401.         state = COPY;
  402.  
  403.         /* Look up minimum bits to encode distance */
  404.         for (i = 0; i<COPYRANGES; i++) {
  405.           if (distance <= copymax[i]) {
  406.             compress(output,FIRSTCODE-MINCOPY+len+i*CODESPERRANGE);
  407.             output_code(output,distance-copymin[i],copybits[i]);
  408.             break;
  409.           }
  410.         }
  411.       }
  412.       else   /* Else output single literal character */
  413.         compress(output,buffer[n]);
  414.     }
  415.  
  416.     /* Advance buffer pointers */
  417.     if (++n == maxsize) n = 0;
  418.     if (++addpos == maxsize) addpos = 0;
  419.  
  420.     /* Add next input character to buffer */
  421.     if (c != EOF) {
  422.       if ((c = getc(input)) != EOF) {
  423.         buffer[insert++] = c;  ++bytes_in;
  424.       } else full = 0;
  425.       if (insert == maxsize) {
  426.         insert = 0; full = 1;
  427.       }
  428.     }
  429.   }
  430.  
  431.   /* Output EOF code and free memory */
  432.   compress(output,TERMINATE);
  433.   flush_bits(output);
  434.   farfree(head); farfree(tail); farfree(succ); farfree(pred);
  435.   free(buffer);
  436. }
  437.  
  438. /* Decode file from input to output */
  439. decode(input,output)
  440.   FILE *input,*output;
  441. {
  442.   int c, i, j, k, dist, len, n = 0, index;
  443.  
  444.   initialize();
  445.   buffer = (unsigned char *) malloc(maxsize*sizeof(unsigned char));
  446.   if (buffer == NULL) {
  447.     printf("Error allocating memory\n");
  448.     exit(1);
  449.   }
  450.   while ((c = uncompress(input)) != TERMINATE) {
  451.     if (c < 256) {     /* Single literal character ? */
  452.       putc(c,output);
  453.       ++bytes_out;
  454.       buffer[n++] = c;
  455.       if (n == maxsize) n = 0;
  456.     } else {            /* Else string copy length/distance codes */
  457.       index = (c - FIRSTCODE)/CODESPERRANGE;
  458.       len = c - FIRSTCODE + MINCOPY - index*CODESPERRANGE;
  459.       dist = input_code(input,copybits[index]) + len + copymin[index];
  460.       j = n; k = n - dist;
  461.       if (k < 0) k += maxsize;
  462.       for (i = 0; i<len; i++) {
  463.         putc(buffer[k],output);  ++bytes_out;
  464.         buffer[j++] = buffer[k++];
  465.         if (j == maxsize) j = 0;
  466.         if (k == maxsize) k = 0;
  467.       }
  468.       n += len;
  469.       if (n >= maxsize) n -= maxsize;
  470.     }
  471.   }
  472.   free(buffer);
  473. }
  474.  
  475. /* Main program */
  476. main(argc,argv)
  477.   int argc;
  478.   char *argv[];
  479. {
  480.   FILE *infile, *outfile;
  481.  
  482.   if (argc < 3 || argc > 4)
  483.     printf("Usage: %s inputfile outputfile [decompress]\n",argv[0]);
  484.   else if (!strcmp(argv[1],argv[2]))
  485.     printf("File names must be different\n");
  486.   else if ((infile = fopen(argv[1],"rb")) == NULL)
  487.     printf("Error opening input file %s\n",argv[1]);
  488.   else if ((outfile = fopen(argv[2],"wb")) == NULL)
  489.     printf("Error opening output file %s\n",argv[2]);
  490.   else {
  491.     if (argc == 3) {
  492.       encode(infile,outfile);
  493.       printf("Packed from %ld bytes to %ld bytes\n",bytes_in,bytes_out);
  494.     } else {
  495.       decode(infile,outfile);
  496.       printf("Unpacked from %ld bytes to %ld bytes\n",bytes_in,bytes_out);
  497.     }
  498.     fclose(outfile); fclose(infile);
  499.   }
  500. }
  501. 
  502.  
  503.  
  504.  
  505.